﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FindGreatestLinkedNode.Question;
namespace FindGreatestLinkedNode.Answer
{
    public class Libby : IFindNearestGreatestNodeInBinaryTree
    {
        public int? FindNearestGreatestNode(Node root, int k)
        {
            if (root == null)
            {
                return null;
            }
            else if (root.LeftChild == null && root.RightChild == null)
            {
                return null;
            }

            int currentMax;
            if (root.Data == k)
            {
                currentMax = root.Data;
                if (root.LeftChild != null && root.LeftChild.Data > currentMax)
                {
                    currentMax = root.LeftChild.Data;
                }

                if (root.RightChild != null && root.RightChild.Data > currentMax)
                {
                    currentMax = root.RightChild.Data;
                }
            }
            else
            {

                Node KFather = FindK(root, k);
                if (KFather == null)
                {
                    return null;
                }

                Node Knode = null;
                if (KFather.LeftChild != null && KFather.LeftChild.Data == k)
                {
                    Knode = KFather.LeftChild;
                }
                else Knode = KFather.RightChild;

                currentMax = Knode.Data > KFather.Data ? Knode.Data : KFather.Data;
                if (Knode.LeftChild != null && Knode.LeftChild.Data > currentMax)
                {
                    currentMax = Knode.LeftChild.Data;
                }
                if (Knode.RightChild != null && Knode.RightChild.Data > currentMax)
                {
                    currentMax = Knode.RightChild.Data;
                }
            }

            //If Knode should be considered.
            return currentMax;

            //If Knode should not be considered.
            //if (currentMax != k)
            //{
            //    return currentMax;
            //}
            //else
            //    return null;
        }

        Node FindK(Node root, int k)
        {
            if (root == null)
            {
                return null;
            }
            else if ((root.LeftChild != null && root.LeftChild.Data == k) || (root.RightChild != null && root.RightChild.Data == k))
            {
                return root;
            }

            Node LeftResult = FindK(root.LeftChild, k);
            Node RightResult = FindK(root.RightChild, k);

            if (LeftResult != null)
            {
                return LeftResult;
            }
            else if (RightResult != null)
            {
                return RightResult;
            }
            else
            {
                return null;
            }
        }
    }
}